from typing import List

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = dp = [0] * (len(s) + 1)

        dp[0] = 1
        for i in range(0, len(s)):
            for j in range(i + 1,len(s)+1):
                if s[i:j] in wordDict:
                    print(i,j,s[i:j])
                    if i - 1 < 0:
                        dp[j] = 1
                    else:
                        if dp[j] != 1:
                            dp[j] = dp[i]
                    print(dp)
                
        print(dp)
        return dp[len(s)] == 1

    
    
    def check(self, dp, i, j):
        if i == len(dp[0]):
            return True
        
        for k in range(len(dp[i])):
            if dp[i][k] == 1:
                self.check(dp, k, j)
        return False

if __name__ == '__main__':
    s = Solution()
    print(s.wordBreak("aaaaaaa", ["aaaa","aaa"]))